# include <iostream>
# include <cstdio>
# include <vector>
# define MAXN 100023
using namespace std;

vector <int> to[MAXN];
long long siz[MAXN], dfn[MAXN], cnt, n, q, a[MAXN], adfn[MAXN];
char op[23];

struct edge { 
    long long fr, to;
    edge () {
        fr = to = 0;
    }
    edge (long long a, long long b) { 
        fr = a, to = b;
    }
} e[MAXN];

struct node { 
    long long mx, mi;
    node *ls, *rs;
    node () { 
        mx = 0;
        mi = 0x7fffffff;
        ls = rs = NULL;
    }
} *root;

# define mid ((l + r) >> 1)
node *build(long long l, long long r) { 
    node *x = new node();
    if (l ^ r) { 
        x->ls = build(l, mid);
        x->rs = build(mid + 1, r);
        x->mi = min(x->ls->mi, x->rs->mi);
        x->mx = max(x->ls->mx, x->rs->mx);
    } else { 
      x->mi = x->mx = a[dfn[l]];
    }
    return x;
}

long long query(node *x, long long l, long long r, long long s, long long t, bool m) { 
    if(l == s && r == t) { 
        return (m) ? x->mx : x->mi;
    } else { 
        if(t <= mid) return query(x->ls, l, mid, s, t, m);
        if(s > mid) return query(x->rs, mid + 1, r, s, t, m);
        if(m) { 
            return max(query(x->ls, l, mid, s, mid, m), query(x->rs, mid + 1, r, mid + 1, t, m));
        } else return min(query(x->ls, l, mid, s, mid, m), query(x->rs, mid + 1, r, mid + 1, t, m));
    }
}

void change(node *x, long long l, long long r, long long k, long long p) { 
    if(l == r) { 
        x->mi = x->mx = p;
    } else { 
        if(k <= mid) change(x->ls, l, mid, k, p);
        else change(x->rs, mid + 1, r, k, p);
        x->mi = min(x->ls->mi, x->rs->mi);
        x->mx = max(x->ls->mx, x->rs->mx);
    }
}

void dfs(long long x) { 
    siz[x] = 1;
    dfn[++cnt] = x;
    adfn[x] = cnt;
    for(long long i = 0; i < to[x].size(); i++) { 
        if(siz[to[x][i]]) continue;
        else dfs(to[x][i]);
        siz[x] += siz[to[x][i]];
    }
}

int main() { 
    //freopen("westward.in", "r", stdin);
    //freopen("westward.out", "w", stdout);
    scanf("%lld %lld", &n, &q);
    for(long long i = 1; i <= n; i++) scanf("%lld", a + i);
    for(long long i = 1; i < n; i++) { 
        long long a, b;
        scanf("%lld %lld", &a, &b);
        to[a].push_back(b);
        to[b].push_back(a);
        e[i] = edge(a, b);
    }
    dfs(1);
    root = build(1, n);
    for(long long i = 1; i <= q; i++) { 
        scanf("%s", op);
        if(op[0] == 'C') { 
            long long a, b;
            scanf("%lld %lld", &a, &b);
            change(root, 1, n, adfn[a], b);
        } else { 
            long long j;
            scanf("%lld", &j);
            long long s = e[j].fr, t = e[j].to;
            if(siz[s] < siz[t]) swap(s, t); // s -> t
            long long min1 = 0x7fffffff, min2 = 0x7fffffff, max1 = 0, max2 = 0;
            long long l = adfn[t];
            long long r = adfn[t] + siz[t] - 1;
            min1 = query(root, 1, n, l, r, 0);
            max1 = query(root, 1, n, l, r, 1);
            if(l != 1) { 
                min2 = min(query(root, 1, n, 1, l - 1, 0), min2);
                max2 = max(query(root, 1, n, 1, l - 1, 1), max2);
            } 
            if(r != n) { 
                min2 = min(query(root, 1, n, r + 1, n, 0), min2);
                max2 = max(query(root, 1, n, r + 1, n, 1), max2);
            }
            printf("%lld\n", min1 * max1 + min2 * max2);
        }
    }
}
